package cn.edu.jxau.test;

import java.util.Arrays;

import cn.edu.jxau.util.LinkedStack;
import cn.edu.jxau.util.Stack;

/**
 * @author Fudashi
 */
public class Main {

	public static void main(String[] args) {

		Integer[] a = new Integer[] { 12, 43, 65, 87, 94, 95 };
		LinkedList<Integer> list = new LinkedList<>(a);
		list.reverse();
		list.reversePrint();
	}

}

class LinkedList<T> {

	private Node first = new Node();

	public LinkedList(T[] arr) {
		for (T item : arr) {
			add(item);
		}
	}

	private void add(T data) {

		Node node = new Node(data);
		Node cur = first;
		while (cur.next != null) {
			cur = cur.next;
		}
		cur.next = node;
	}

	/**
	 * 逆序打印
	 */
	public void reversePrint() {

		Stack<T> stack = new LinkedStack<>();
		Node cur = first.next;
		while (cur != null) {
			stack.push(cur.data);
			cur = cur.next;
		}
		while (!stack.isEmpty()) {
			System.out.print(stack.pop() + "\t");
		}
	}

	public void reverse() {
		first.next = reverse(first.next);
	}

	/**
	 * 链表就地逆序
	 */
//	private Node reverse(Node first) {
//
//		Node reverse = null;
//		while (first != null) {
//			Node second = first.next;
//			first.next = reverse;
//			reverse = first;
//			first = second;
//		}
//		return reverse;
//	}

	/**
	 * 链表就地逆序（递归版）
	 */
	private Node reverse(Node first) {

		if (first == null) {
			return null;
		}
		if (first.next == null) {
			return first;
		}
		Node second = first.next;
		Node reverse = reverse(second);
		second.next = first;
		first.next = null;
		return reverse;

	}

	private class Node {
		private Node next;
		private T data;

		public Node() {

		}

		public Node(T data) {
			this.data = data;
		}
	}
}